package 一些算法竞赛测试题;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: a
 * Date: 2022-10-26
 * Time: 14:18
 */
class TreeNode {
    int val;
     TreeNode left;
   TreeNode right;
    TreeNode() {}
     TreeNode(int val) { this.val = val; }
   TreeNode(int val, TreeNode left, TreeNode right) {
       this.val = val;
        this.left = left;
        this.right = right;
     }
}

public class Demo16 {
    public static int minimumOperations(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            int[] q = new int[size + 1];
            boolean[] st = new boolean[100010];
            boolean[] b = new boolean[100010];
            for(int i = 1; i <= size; i++){
                TreeNode t = queue.poll();
                q[i] = t.val;
                b[q[i]] = true;
                if(t.left != null){
                    queue.offer(t.left);
                }
                if(t.right != null){
                    queue.offer(t.right);
                }
            }
            int cnt = 0;
            for(int i = 1; i <= size; i++){
                int t = q[i];
                if(!st[t]){
                    cnt++;
                    int j = t;
                    while(b[j] && !st[j]){
                        st[j] = true;
                        if(j <= size){
                            j = q[j];
                        }
                    }
                }
            }
            res += size - cnt;
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(7);
        root.left.right = new TreeNode(6);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(4);
        minimumOperations(root);
    }
}
